import java.util.*;

/**
 * 146. LRU缓存机制
 * https://leetcode-cn.com/problems/lru-cache/
 */
public class Solutions_146 {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        int res1 = cache.get(1);  // output: 1
        System.out.println(res1);
        cache.put(3, 3);  // 该操作会使得关键字 2 作废
        int res2 = cache.get(2);  // output: -1
        System.out.println(res2);
        cache.put(4, 4);  // 该操作会使得关键字 1 作废
        int res3 = cache.get(1);  // output: -1
        System.out.println(res3);
        int res4 = cache.get(3);  // output: 3
        System.out.println(res4);
        int res5 = cache.get(4);  // output: 4
        System.out.println(res5);
    }
}

/**
 * 解法二:双向链表 + 哈希表实现（手写 LinkedHashMap 实现）（20ms）
 * 为什么用双向链表?
 *  对于某一结点,需要知道其前一结点和后一结点
 * 为什么用哈希表?
 *  需要使用键值对形式存储
 */
class LRUCache {
    // 双向链表类
    class MyLinkedNode {
        int key;
        int val;
        MyLinkedNode prev;
        MyLinkedNode next;

        public MyLinkedNode() {

        }

        public MyLinkedNode(int _key, int _value) {
            key = _key;
            val = _value;
        }
    }

    private Map<Integer, MyLinkedNode> cache = new HashMap<>();
    // 已存储的元素个数
    private int size;
    // 缓存容量
    private int capacity;
    // 定义双向链表的初始头,尾结点(链表头部记录使用频繁的元素,尾部记录使用较少的元素)
    private MyLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new MyLinkedNode();
        tail = new MyLinkedNode();
        // 头尾结点关联(头结点的后继结点指向尾结点,尾结点的前驱结点指向头结点)
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        MyLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 最近使用过,将 node 移动到链表头部
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        MyLinkedNode node = cache.get(key);
        if (node == null) {
            // key 不存在时,创建一个节点
            MyLinkedNode newNode = new MyLinkedNode(key, value);
            // 记录到哈希表中
            cache.put(key, newNode);
            // 添加到双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 大小超出缓存容量,移除不常用的元素
                // 从链表中移除尾部结点
                MyLinkedNode tailNode = removeTail();
                // 再根据 key 从哈希表中移除
                cache.remove(tailNode.key);
                // 大小减 1
                --size;
            }
        } else {
            // key 存在时,修改 value 值,再移动到链表头部
            node.val = value;
            moveToHead(node);
        }
    }

    /**
     * 将 node 结点,移动到链表头结点
     * 1. 移除操作
     * 2. 添加操作
     * @param node
     */
    private void moveToHead(MyLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 移除尾结点
     * 虚拟尾节点 tail 的前驱节点,即是真实尾结点
     * @return
     */
    private MyLinkedNode removeTail() {
        MyLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    /**
     * 移除结点
     * 1. 将删除结点的后继结点,成为其前驱结点的后继结点
     * 2. 将删除结点的前驱结点,成为其后继结点的前驱结点
     * @param node
     */
    private void removeNode(MyLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 添加 node 结点到头结点
     * 1. node 的前驱结点,指向 head
     * 2. node 的后继结点,指向 head.next
     * 3. head.next 的前驱结点,指向 node
     * 4. head 的后继结点,指向 node
     * @param node
     */
    private void addToHead(MyLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
}

/**
 * 解法一:LinkedHashMap 实现（16ms）
 * 其中提供了 removeEldestEntry 方法,可以删除链表中最老(使用频率最小)的键和值
 */
class LRUCache2 extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache2(int capacity) {
        // 如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序
        // 如果accessOrder为flase的话，则按插入顺序来遍历
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        // 继承时定义泛型后，get 时不需要进行强制类型转换
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // put 操作后,进入方法
        // 若 return true,便移除 map 中最老的键和值
        // 超过缓存容量时,移除 map 中最老的键和值
        return size() > capacity;
    }
}